package com.leetcode.p400;

import com.bean.TreeNode;
import com.utils.TreeUtils;

public class Test437_baoli {

    public int pathSum(TreeNode root, int targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }

        ret += rootSum(root, targetSum);

        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);

        return ret;
    }

    private int rootSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;

        int val = root.val;
        if (targetSum == val) {
            ret++;
        }

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);

        return ret;
    }


    public static void main(String[] args) {
        TreeNode treeNode = TreeUtils.buildTree("10,5,-3,3,2,null,11,3,-2,null,1");
        TreeUtils.showTree(treeNode);
        Test437_baoli test = new Test437_baoli();
        System.out.println(test.pathSum(treeNode, 8));
    }
}
